package com.leetcode;

public class Leetcode069 {

    public int mySqrt(int x) {
        int left = 0;
        int right = x;
        int ans = -1;
        int mid = -1;

        //一直循环到左右边界重合
        while(left<=right){
            //为什么不是(right+left)/2，防止right+left数值越界
            mid = left+(right-left)/2;
            if(x >= (long)mid*mid){
                ans = mid;
                left = mid + 1;
            }else{
                right = mid -1;
            }
        }

        return ans;
    }


    public static void main(String[] args) {
        Leetcode069 leetcode069 = new Leetcode069();
        System.out.println(leetcode069.mySqrt(9));
    }
}
